Software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. A transaction in the context of transactional memory is a piece of code that executes a series of reads and writes to shared memory. A data value in the context of transactional memory is the particular segment of shared memory being accessed, such as a single object, a cache line (such as in C++), a virtual memory page, a single word, etc.
Software transactional memory is designed to ease development of concurrent programs by providing atomicity and isolation to regions of program code. Some STM systems extend this capability with an operation called “retry” that allows basic communication between transactions. When a transaction executes a retry operation, its effects are rolled back and execution is suspended until something that the transaction read changes. When a change is detected, the transaction is re-executed. Retry operations can be used for some very common data structures, like blocking queues. For example, a transaction could check to see if a queue is empty and then retry if it is empty, or remove an element if the queue is not empty. The transaction will block while the queue remains unchanged and re-execute when the state of the queue changes, which gives the transaction another opportunity to complete. The problem with implementations of this retry operation in current STM systems is that they impose a lot of overhead on the operation of all transactions in the system, even if no transactions are executing a retry operation. Some systems, for example, perform a compare and swap (CAS) on every write lock release, and these CAS operations are expensive. Other systems require that an entire nest of transactions are rolled back if a small, deeply-nested transaction executes a retry operation, which can be very inefficient.